#include "main/utils.h"
using namespace std;

map<long, vector<string>> groupAnagrams(const vector<string> &vec) {
  vector<int> hash = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                      43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
  map<long, vector<string>> ret;
  for (int i = 0; i < vec.size(); ++i) {
    long mul = 1;
    for (int j = 0; j < vec[i].size(); ++j) {
      int idx = vec[i][j] - 'a';
      mul *= hash[idx];
    }
    ret[mul].push_back(vec[i]);
  }
  return ret;
}

map<string, vector<string>> groupAnagrams1(vector<string> vec) {
  map<string, vector<string>> ret;
  for (int i = 0; i < vec.size(); ++i) {
    auto temp_string = vec[i];
    sort(vec[i].begin(), vec[i].end());
    ret[vec[i]].push_back(temp_string);
  }
  return ret;
}

template <typename T>
void printResult(T ret) {
  for (auto ele : ret) {
    for (int i = 0; i < ele.second.size(); ++i) {
      cout << ele.second[i] << " ";
    }
    cout << endl;
  }
}

int main() {
  vector<string> vec = {"eat", "tea", "tan", "ate", "nat", "bat"};
  auto ret = groupAnagrams(vec);
  printResult(ret);

  cout << "====================" << endl;
  auto ret1 = groupAnagrams1(vec);
  printResult(ret1);

  return 0;
}
